1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| #include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define int long long
const int maxn = 2005;
const int S = 0;
const int T = 4001;
const int INF = 0x3f3f3f3f3f3f3f3fll;
using namespace std;
struct E{
int to, nxt, f, c;
}e[maxn << 4]; int head[maxn << 1], tot = 1;
void addedge(int u, int v, int f, int c){
e[++tot].to = v, e[tot].nxt = head[u], e[tot].f = f, e[tot].c = c;
head[u] = tot;
}
void ins(int u, int v, int f, int c){
addedge(u, v, f, c);
addedge(v, u, 0, -c);
}
bool inq[maxn << 1]; int pre[maxn << 1], dis[maxn << 1], flow[maxn << 1], last[maxn << 1];
bool SPFA(){
memset(dis, 0x3f, sizeof dis); memset(flow, 0x3f, sizeof flow); memset(inq, 0, sizeof inq);
queue <int> q; while (!q.empty()) q.pop(); q.push(S);
inq[S] = 1, dis[S] = 0; pre[T] = -1;
while (!q.empty()){
int cur = q.front(); q.pop(); inq[cur] = 0;
for (int i = head[cur]; i; i = e[i].nxt){
int v = e[i].to;
if (e[i].f > 0 && dis[v] > dis[cur] + e[i].c){
dis[v] = dis[cur] + e[i].c;
flow[v] = min(flow[cur], e[i].f);
pre[v] = cur;
last[v] = i;
if (!inq[v]){
inq[v] = 1; q.push(v);
}
}
}
}
return pre[T] != -1;
}
int maxflow, mincost;
void work(){
while (SPFA()){
int cur = T;
maxflow += flow[T];
mincost += flow[T] * dis[T];
while (cur != S){
e[last[cur]].f -= flow[T];
e[last[cur] ^ 1].f += flow[T];
cur = pre[cur];
}
}
}
int n, tf, f, ts, s, p, x[maxn];
signed main(){
scanf("%lld", &n);
for (int i = 1; i <= n; i++) scanf("%lld", x + i);
scanf("%lld%lld%lld%lld%lld", &p, &tf, &f, &ts, &s);
for (int i = 1; i <= n; i++) ins(S, i + n, INF, p), ins(i + n, T, x[i], 0);
for (int i = 1; i <= n; i++){
if (i != n) ins(i, i + 1, INF, 0);
ins(S, i, x[i], 0);
if (i + tf <= n) ins(i, i + tf + n, INF, f);
if (i + ts <= n) ins(i, i + ts + n, INF, s);
}
work();
printf("%lld\n", mincost);
return 0;
}
|